

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

using Node = TreeNode;

class Solution
{
public:
    int subarraySum(vector<int>& nums, int k)
    {
        int res = 0;
        int sum = 0;
        int n = nums.size();
        unordered_map<int, int> hash;

        ++hash[0];
        for (int i = n - 1; i >= 0; --i)
        {
            sum += nums[i];
            if (hash[sum - k])
                res += hash[sum - k];
            ++hash[sum];
        }

        return res;
    }
    
    int subarraysDivByK(vector<int>& nums, int k)
    {
        int res = 0;
        int sum = 0;
        int n = nums.size();
        unordered_map<int, int> hash({ {0, 1} });

        for (const auto i : nums)
        {
            sum += i;
            int mod = ((sum % k) + k) % k;

            if (hash[mod])
                res += hash[mod];
            ++hash[mod];
        }

        return res;
    }

    int findMaxLength(vector<int>& nums)
    {
        int res = 0;
        int sum = 0, n = nums.size();
        unordered_map<int, int> hash({ {0, -1} });

        for (int i = 0; i < n; ++i)
        {
            if (nums[i])
                sum += 1;
            else
                sum += -1;

            if (hash.count(sum))
                res = max(res, i - hash[sum]);
            else
                hash[sum] = i;
        }

        return res;
    }

    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        int n = nums.size();

        return _sortedArrayToBST(nums, 0, n - 1);
    }

private:
    Node* _sortedArrayToBST(const vector<int>& nums, int lf, int rg)
    {
        if (lf > rg)
            return nullptr;

        int mid = lf + ((rg - lf) >> 1);
        Node* root = new Node(nums[mid]);

        root->left = _sortedArrayToBST(nums, lf, mid - 1);
        root->right = _sortedArrayToBST(nums, mid + 1, rg);

        return root;
    }
};

int main()
{


	return 0;
}